/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 *思路：中序遍历将二叉树变成双向链表
 */
class TreeToDoublyList {
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }
        LinkList(root);
        Node head=root;
        while(head.left!=null){
            head=head.left;
        }
        Node tail=root;
        while(tail.right!=null){
            tail=tail.right;
        }
        head.left=tail;
        tail.right=head;
        return head;
    }
    Node pre=null;
    public void LinkList(Node root){
        if(root==null){
            return ;
        }
       LinkList(root.left);
        root.left=pre;
        if(pre!=null){
            pre.right=root;
        }
        pre=root;
        LinkList(root.right);
    }
}